#include  <iostream>
#include  <cstring>
#include  <limits.h>
using namespace std;

void merge(int *arr, int p, int q, int r)
{
	int len = r - p + 1;
	int *a = new int[q-p];
	int *b = new int[r-q+1];

	memcpy(a,&arr[p],sizeof(int) * (q-p));
	memcpy(b,&arr[q],sizeof(int) * (r-q+1));

	int index = p;
	int i = 0, j = 0;
	bool a_empty = false, b_empty = false;

	while( true )
	{
		if( i-1 == q-p-1 )
		{
			a_empty = true;
			break;
		}
		if( j-1 == r-q )
		{
			b_empty = true;
			break;
		}

		if( a[i] < b[j] )
			arr[index++] = a[i++];
		else
			arr[index++] = b[j++];
	}

	if( a_empty && !b_empty )
		memcpy(&arr[index],b+j,sizeof(int)*(r-q+1-j));
	else if( b_empty && !a_empty )
		memcpy(&arr[index],a+i,sizeof(int)*(q-p-i));

}

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void _msort(int *arr, int p, int r)
{
	if(p >= r)
		return;

	if( p + 1 == r )
	{
		if(arr[p] > arr[r])
			swap(&arr[p],&arr[r]);

		return;
	}
	int q = (r + p)/2;
	_msort(arr,p,q-1);
	_msort(arr,q,r);
	merge(arr,p,q,r);
}

void msort(int *arr, size_t n)
{
	if(n == 1)
		return;

	_msort(arr,0,n-1);
}

int main(int argc, char *argv[])
{
	int a[10] = {9,7,8,10,12,5,4,3,2,1};

	msort(a,10);

	for( int i = 0 ; i < 10 ; ++i )
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
